﻿#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
	vector<int> preorderTraversal(TreeNode* root) {
		stack<TreeNode*> s;
		vector<int> v;
		TreeNode* cur = root;
		while (cur || !s.empty())
		{
			// 访问⼀颗树的开始
			// 1、访问左路结点，左路结点⼊栈
			while (cur)
			{
				v.push_back(cur->val);
				s.push(cur);
				cur = cur->left;
			}
			// 2、从栈中依次访问左路结点的右⼦树
			TreeNode* top = s.top();
			s.pop();
			// 循环⼦问题⽅式访问左路结点的右⼦树 --
			cur = top->right;
		}
		return v;
	}
};
class Solution {
public:
	vector<int> inorderTraversal(TreeNode* root) {
		stack<TreeNode*> st;
		TreeNode* cur = root;
		vector<int> v;
		while (cur || !st.empty())
		{
			// 访问⼀颗树的开始
			// 1、左路结点⼊栈
			while (cur)
			{
				st.push(cur);
				cur = cur->left;
			}
			// 访问问左路结点 和 左路结点的右⼦树
			TreeNode* top = st.top();
			st.pop();
			v.push_back(top->val);
			// 循环⼦问题⽅式访问右⼦树
				cur = top->right;
		}
		return v;
	}
};
class Solution {
public:
	vector<int> postorderTraversal(TreeNode* root) {
		TreeNode* cur = root;
		stack<TreeNode*> s;
		vector<int> v;
		TreeNode* prev = nullptr;
		while (cur || !s.empty())
		{
			// 1、访问⼀颗树的开始
			while (cur)
			{
				s.push(cur);
				cur = cur->left;
			}
			TreeNode* top = s.top();
			// top结点的右为空 或者 上⼀个访问结点等于他的右孩⼦
			// 那么说明(空)不⽤访问 或者 (不为空)右⼦树已经访问过了
			// 那么说明当前结点左右⼦树都访问过了，可以访问当前结点了
			if (top->right == nullptr || top->right == prev)
			{
				s.pop();
				v.push_back(top->val);
				prev = top;
			}
			else
			{
				// 右⼦树不为空，且没有访问，循环⼦问题⽅式右⼦树
				cur = top->right;
			}
		}
		return v;
	}
};